﻿#include "bpt.h"
#include <deque>

using namespace std;

LockUtil::LockUtil(BPTree* bpt, bool rw) :
	__bpt(bpt), __rw(rw) {
	if (__rw)
		__bpt->__r_entry();
	else
		__bpt->__w_entry();
}

LockUtil::~LockUtil() {
	if (__rw)
		__bpt->__r_leave();
	else
		__bpt->__w_leave();
}


BPTree::BPTree(int b, int l) :
	branchs(b), leaf_cap(l) {
	meta_root = new BPTLeaf(leaf_cap);
	/*insert_ret = true;
	remove_ret = true;*/
	r_count = 0;
}

void BPTree::__insert(BPTNode* root, unsigned long key, unsigned long val, bool& insert_ret) {

	// 叶子节点直接插入
	if (root->is_leaf()) {
		insert_ret = ((BPTLeaf*)root)->insert(key, val);
		return;
	}

	// 非叶子节点
	BPTInnerNode* inner_node = (BPTInnerNode*)root;
	int loc;
	// key的右分支的所有值是大于等于key的
	// 返回值为true，则loc需要加1，选择该key的右分支
	// false，返回值就是key可能位于的分支
	if (bn_search(inner_node->keys, key, inner_node->size, loc))
		loc++;
	BPTNode* sub_node = inner_node->nodes[loc];
	__insert(sub_node, key, val, insert_ret);
	// 非重复元插入成功
	if (insert_ret) {
		// 溢出分裂
		if (sub_node->spilled()) {
			unsigned long min_key;
			BPTNode* splitted_node = sub_node->split(min_key);
			// 插入当前节点
			inner_node->insert(loc, min_key, splitted_node, false);
		}
	}
}

bool BPTree::insert(unsigned long key, unsigned long val) {
	// 写锁
	LockUtil lu(this, false);
	
	bool insert_ret = true;
	__insert(meta_root, key, val, insert_ret);
	if (insert_ret) {
		// 溢出则分裂
		if (meta_root->spilled()) {
			unsigned long min_key;
			BPTNode* splitted_node = meta_root->split(min_key);
			BPTInnerNode* new_root = new BPTInnerNode(branchs);
			new_root->insert_first(min_key, meta_root, splitted_node);
			meta_root = new_root;
		}

		__size++;
		return true;
	}

	// 重复元
	return false;
}

BPTree::BPTree():BPTree(9, 16) {

}

BPTree::~BPTree() {
	__clear(meta_root);
}

void BPTree::__remove(BPTNode* root, unsigned long key, bool& remove_ret) {
	// 叶子节点直接删除
	if (root->is_leaf()) {
		remove_ret = root->remove(key);
		return;
	}

	// 非叶子节点
	BPTInnerNode* inner_node = (BPTInnerNode*)root;
	int loc;
	// key的右分支的所有值是大于等于key的
	if (bn_search(inner_node->keys, key, inner_node->size, loc))
		loc++;
	BPTNode* sub_node = inner_node->nodes[loc];
	__remove(sub_node, key, remove_ret);
	// 删除成功
	if (remove_ret) {
		// 小于半满时
		if (sub_node->concealed()) {
			// 找具有最大size的兄弟节点
			int silbing_loc = -1;
			if (loc - 1 >= 0 && loc + 1 <= inner_node->size) {
				silbing_loc = inner_node->nodes[loc - 1]->size >
					inner_node->nodes[loc + 1]->size ? loc - 1 : loc + 1;
			}
			if (silbing_loc == -1) silbing_loc = loc - 1;
			if (silbing_loc < 0) silbing_loc = loc + 1;

			BPTNode* silbing_node = inner_node->nodes[silbing_loc];
			// 判断是向左还是右兄弟节点借
			bool l_r = false;
			int mid_key_loc = loc;
			if (silbing_loc == loc - 1) {
				l_r = true;
				mid_key_loc = loc - 1;
			}

			// 兄弟节点少一个仍然半满
			if (!silbing_node->concealed(silbing_node->size - 1)) {
				// 向兄弟节点借一个元素，并更新父节点的key
				inner_node->keys[mid_key_loc] = 
					sub_node->borrow(silbing_node, inner_node->keys[mid_key_loc], l_r);
			}
			else {
				// 兄弟节点不能借则和兄弟节点合并
				if (l_r) {
					silbing_node->append(sub_node, inner_node->keys[mid_key_loc]);
					delete sub_node;
					sub_node = silbing_node;
				}
				else {
					sub_node->append(silbing_node, inner_node->keys[mid_key_loc]);
					delete silbing_node;
				}
				inner_node->__remove(mid_key_loc, false);
			}
		}
	}
}

bool BPTree::remove(unsigned long key) {
	// 写锁
	LockUtil lu(this, false);
	if (!meta_root->size)
		return false;
	bool remove_ret = true;
	__remove(meta_root, key, remove_ret);
	if (remove_ret) {
		// 只剩下一个节点
		if (!meta_root->is_leaf() && !meta_root->size) {
			BPTInnerNode* org_node = (BPTInnerNode*)meta_root;
			meta_root = org_node->nodes[0];
			delete org_node;
		}
		__size--;
		return true;
	}
	// 未找到
	return false;
}

void BPTree::__contain(BPTNode* root, unsigned long key, bool& contain_ret) {
	if (root->is_leaf()) {
		contain_ret = root->contain(key);
		return;
	}

	// 非叶子节点
	BPTInnerNode* inner_node = (BPTInnerNode*)root;
	int loc;
	// key的右分支的所有值是大于等于key的
	if (bn_search(inner_node->keys, key, inner_node->size, loc))
		loc++;
	BPTNode* sub_node = inner_node->nodes[loc];
	__contain(sub_node, key, contain_ret);

}

bool BPTree::contain(unsigned long key) {
	// 读锁
	LockUtil lu(this, true);
	if (!meta_root->size) return false;
	bool contain_ret = true;
	__contain(meta_root, key, contain_ret);
	return contain_ret;
}

int BPTree::size() const{
	return __size;
}

void BPTree::__clear(BPTNode* root) {
	if (!root->is_leaf()) {
		for (int i = 0; i <= root->size; i++) {
			__clear(((BPTInnerNode*)root)->nodes[i]);
		}
	}
	
	delete root;
}

void BPTree::clear() {
	// 写锁
	LockUtil lu(this, false);
	__clear(meta_root);
	__size = 0;
	meta_root = new BPTLeaf(leaf_cap);
}

void BPTree::__serialize(BPTNode* root, ofstream& outfs) {
	/*DFS序列化节点，并写入*/
	int seria_len;
	char* seria = root->serialize(seria_len);
	outfs.write(seria, seria_len);
	delete[] seria;

	// 非叶子则递归
	if (!root->is_leaf()) {
		for (int i = 0; i <= root->size; i++) {
			__serialize(((BPTInnerNode*)root)->nodes[i], outfs);
		}
	}
}

void BPTree::serialize(const string& filename) {
	// 读锁
	LockUtil lu(this, true);
	ofstream outfs(filename, ios::out | ios::binary);
	// 按字符写的，不能使用
	//outfs << branchs << leaf_cap;
	outfs.write((char*)&branchs, sizeof(int));
	outfs.write((char*)&leaf_cap, sizeof(int));
	outfs.write((char*)&__size, sizeof(int));
	__serialize(meta_root, outfs);
	outfs.close();
}

void BPTree::__load(BPTNode*& root, ifstream& infs, bool& load_ret) {
	int len;
	infs.read((char*)&len, sizeof(len));
	char* serialization = new char[len];
	char* org_seria = serialization;
	((int*)serialization)[0] = len;
	serialization += sizeof(int);
	infs.read(serialization, len - sizeof(int));

	root = BPTNode::deserialize(org_seria, branchs, leaf_cap);
	delete[] org_seria;

	// 非叶子递归恢复
	if (root) {
		if (!root->is_leaf()) {
			for (int i = 0; i <= root->size; i++) {
				__load(((BPTInnerNode*)root)->nodes[i], infs, load_ret);
				if (!load_ret) {
					return;
				}
			}
		}
	}
	else load_ret = false;
}

bool BPTree::load(const string& filename) {
	// 写锁
	LockUtil lu(this, false);
	__clear(meta_root);
	__size = 0;

	ifstream infs(filename, ios::in | ios::binary);
	infs.read((char*)&branchs, sizeof(int));
	infs.read((char*)&leaf_cap, sizeof(int));
	infs.read((char*)&__size, sizeof(int));
	bool load_ret = true;
	__load(meta_root, infs, load_ret);
	infs.close();
	return load_ret;
}



void BPTree::print() {
	// 读锁
	LockUtil lu(this, true);
	printf("\n-----<BPT branch: %d leaf_cap: %d>\n", branchs, leaf_cap);
	if (!meta_root->size) {
		printf("Empty Tree!!!\n");
		return;
	}

	deque<BPTNode*> que;
	que.push_back(meta_root);

	int level = 1;

	while (!que.empty()) {
		int len = que.size();
		printf("%d: ", level++);
		for (int i = 0; i < len; i++) {
			BPTNode* cur = que.front(); que.pop_front();
			cur->print();
			printf("-->");
			if (!cur->is_leaf()) {
				for (int j = 0; j <= cur->size; j++) {
					que.push_back(((BPTInnerNode*)cur)->nodes[j]);
				}
			}
		}
		printf("\n");
	}

	printf("<BPT End>\n");
}


void BPTree::__r_entry() {
	w_fair_sema.down();
	{
		unique_lock<mutex> lck(r_count_mutex);
		if (!r_count)
			rw_mutex.lock();
		r_count++;
	}
	w_fair_sema.up();
}

void BPTree::__r_leave() {
	unique_lock<mutex> lck(r_count_mutex);
	if (r_count == 1)
		rw_mutex.unlock();
	r_count--;
}

void BPTree::__w_entry() {
	w_fair_sema.down();
	w_fair_sema.up();

	rw_mutex.lock();
}

void BPTree::__w_leave() {
	rw_mutex.unlock();
}